|
In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . The hypothesis states that 3-SAT (or any of several related NP-complete problems) cannot be solved in subexponential time in the worst case.〔.〕 The exponential time hypothesis, if true, would imply that P ≠ NP, but it is a stronger statement. It can be used to show that many computational problems are equivalent in complexity, in the sense that if one of them has a subexponential time algorithm then they all do. ==Definition== ''k''-SAT is the problem of testing whether a Boolean formula, in conjunctive normal form with at most ''k'' variables per clause, can be made to be true by some assignment of Boolean values to its variables. For each integer ''k'' ≥ 2, define a real number ''sk'' to be the infimum of the real numbers δ for which there exists an algorithm solving ''k''-SAT in time O(2δ''n''), where ''n'' is the number of variables in the given ''k''-SAT instance. Then ''s''2 = 0, because 2-SAT can be solved in polynomial time. The exponential time hypothesis is the conjecture that, for every ''k'' > 2, ''s''''k'' > 0. Clearly, ''s''3 ≤ ''s''4 ≤ ..., so it is equivalent to assume that ''s''3 > 0; the positivity of the remaining numbers ''sk'' follows automatically from this assumption. Some sources define the exponential time hypothesis to be the slightly weaker statement that 3-SAT cannot be solved in time 2o(''n''). If there existed an algorithm to solve 3-SAT in time 2o(''n''), then clearly ''s''3 would equal zero. However, it is consistent with current knowledge that there could be a sequence of 3-SAT algorithms, each with running time O(2δ''i''''n'') for a sequence of numbers δ''i'' tending towards zero, but where the descriptions of these algorithms are so quickly growing that a single algorithm could not automatically select and run the most appropriate one.〔.〕 Because the numbers ''s''3, ''s''4, ... form a monotonic sequence that is bounded above by one, they must converge to a limit ''s''∞. The strong exponential time hypothesis (SETH) is the assumption that the limiting value ''s''∞ of the sequence of numbers ''s''''k'' equals one.〔.〕 Another variant is the non-uniform exponential time hypothesis, a strengthening of the second phrasing of the ETH, which posits that there is no family of algorithms (one for each length of the input, in the spirit of advice) that can solve 3-SAT in time 2o(''n''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Exponential time hypothesis」の詳細全文を読む スポンサード リンク
|